package com.cuz.hot100;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

public class Q90SubSet2 {
    LinkedList<List<Integer>> res = new LinkedList<>();
    LinkedList<Integer> tempRes = new LinkedList<>();

    public static void main(String[] args) {
        System.out.println(new Q90SubSet2().subsets1(new int[]{1, 2, 2}));
    }

    public List<List<Integer>> subsets1(int[] nums) {
        if (nums == null || nums.length == 0) {
            return Collections.emptyList();
        }
        int maxLen = nums.length;
        boolean[] hasUse = new boolean[maxLen];
        for (int len = 0; len <= maxLen; len++) {
            if (len > 1 && nums[len-1] == nums[len - 2]) {
                continue;
            }
            process(len, nums, hasUse, 0);
        }
        return res;
    }


    private void process(int maxLen, int[] nums, boolean[] hasUse, int curUse) {
        if (tempRes.size() == maxLen) {
            res.add(new ArrayList<>(tempRes));
        }
        for (int index = curUse; index < nums.length; index++) {
//            if (index > curUse && nums[index] == nums[index - 1]) {
//                continue;
//            }
            if (!hasUse[index]) {
                hasUse[index] = true;
                tempRes.addLast(nums[index]);
                process(maxLen, nums, hasUse, index);
                hasUse[index] = false;
                tempRes.removeLast();
            }
        }
    }

    public List<List<Integer>> subsets2(int[] nums) {
        if (nums == null || nums.length == 0) {
            return Collections.emptyList();
        }
        dfs(0, nums);
        return res;
    }

    private void dfs(int cur, int[] nums) {
        if (cur == nums.length) {
            res.add(new ArrayList<>(tempRes));
            return;
        }
        tempRes.addLast(nums[cur]);
        dfs(cur + 1, nums);
        tempRes.removeLast();
        dfs(cur + 1, nums);
    }
}
